// 给定两个非空的链表l1和l2，分别表示两个非负整数，每位数字都是按照逆序的方式存储的，每个节点存储一位数字
// 要求计算两个非负整数的和，并逆序返回表示和的链表

// 思路：由于链表是逆序存储的，链表头到尾，对应数字位数的低到高
// 时间复杂度：O(max(m, n))，m是链表l1的节点数，n是链表l2的节点数
// 空间复杂度：O(1)

const { LinkedList, ListNode} = require('./64.设计链表')

function addTwoNumbers(head1, head2) {
    let sum = 0
    let curry = 0
    let dummyHead = new ListNode(0, null)
    let cur = dummyHead
    while (head1 || head2 || curry) {
        let num1 = head1?.val || 0
        let num2 = head2?.val || 0
        sum = num1 + num2 + curry
        curry = Math.floor(sum / 10)
        let newNode = new ListNode(sum % 10, null)
        cur.next = newNode
        cur = newNode
        head1 = head1?.next
        head2 = head2?.next
    }
    return dummyHead.next
}

let l1 = new LinkedList([2,4,3,6]).head
let l2 = new LinkedList([5,6,4]).head
// 6342 + 465 = 6807
let result = addTwoNumbers(l1, l2)
console.log(result)
